首页 > 试题广场 >

二叉树的中序遍历

[编程题]二叉树的中序遍历
  • 热度指数：88540 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个二叉树的根节点root，返回它的中序遍历结果。

数据范围：树上节点数满足 ，树上每个节点的值满足 -1000 \le val \le 1000
进阶：空间复杂度 ，时间复杂度
示例1

输入

{1,2,#,#,3}

输出

[2,3,1]

说明
示例2

输入

{}

输出

[]
示例3

输入

{1,2}

输出

[2,1]

说明
示例4

输入

{1,#,2}

输出

[1,2]

说明

备注:
树中节点数目在范围 [0, 100] 内
树中的节点的值在[-100,100]以内

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
Python 3
努力的家家头像 努力的家家
# 指定最大递归深度
import sys
sys.setrecursionlimit(1500)
class Solution:
    l = []
    def inorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        if not root:
            return 
        self.inorderTraversal(root.left)
        self.l.append(root.val)
        self.inorderTraversal(root.right)
        return self.l
发表于 2022-09-13 22:58:32 回复(0)
Python 3
蓝鲸与风头像 蓝鲸与风 
import sys
class Solution:
    res=[]
    def inorderTraversal(self , root: TreeNode) -> List[int]:
        # 由于python存在最大的递归深度约束，这一步是更改最大深度的限制
        sys.setrecursionlimit(1200)#大于树的深度
        if not root:
            return []
        self.inorderTraversal(root.left)
        self.res.append(root.val)
        self.inorderTraversal(root.right)
        return self.res
    

发表于 2022-08-19 09:54:18 回复(1)
Python 3
风软一江山头像 风软一江山 
# 由于python存在最大的递归深度约束，需要更改最大深度的限制
import sys
class Solution:
    def inOrder(self, root, arr):
        if root == None:
            return
        self.inOrder(root.left, arr)
        arr.append(root.val)
        self.inOrder(root.right, arr)
        
    def inorderTraversal(self , root: TreeNode) -> List[int]:
        sys.setrecursionlimit(1500)# 由于python存在最大的递归深度约束，这一步是更改最大深度的限制
        alist = []
        self.inOrder(root, alist)
        return alist

发表于 2022-07-27 19:06:02 回复(0)
Python 3
lun__头像 lun__ 
import sys
sys.setrecursionlimit(100000) #例如这里设置为一百万

class Solution:
    def inorderTraversal(self , root: TreeNode) -> List[int]:
        res = [] 
        def dfs(root):
            nonlocal res 
            if not root: return []
            dfs(root.left)
            res.append(root.val)
            dfs(root.right)
        dfs(root)
        return res 
    

发表于 2022-07-03 16:59:41 回复(0)
Python 3
在求职的斜杠青年很想在家办公头像 在求职的斜杠青年很想在家办公
非遍历方法 
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型一维数组
#
class Solution:
    def inorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        if root is None:
            return []
        inorderSeq = []
        inorderSeq.append(root)
        # 当前节点是否已经经过
        flag = []
        flag.append(False)
        out = []
        
        while inorderSeq:
            node = inorderSeq[-1]
            # 左子树非空或节点未经过，一直入栈，入栈的flag标记为True
            while node.left is not None and not flag[-1]:
                inorderSeq.append(node.left)
                flag[-1] = True
                flag.append(False)
                node = node.left
            
            # 当没有左子树或节点已经过，出栈并且输出
            inorderSeq.pop()
            flag[-1] = True
            out.append(node.val)
            
            # 进入右子树
            if node.right is not None:
                inorderSeq.append(node.right)
                flag.append(False)
            
        return out


发表于 2022-06-15 00:57:17 回复(0)
Python 3
StevenWqq头像 StevenWqq 
import sys
class Solution:
    def inorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        sys.setrecursionlimit(2000) # 不改变递归最大值测试样例会报错
        res = []
        def inorder(root):
            if not root:
                return
            inorder(root.left)
            res.append(root.val)
            inorder(root.right)
                
            return
        
        inorder(root)
        return res

发表于 2022-06-01 13:57:57 回复(0)
Python 3
Vivimore头像 Vivimore

递归

import sys
sys.setrecursionlimit(100000)
class Solution:
    res = []
    def dfs(self, root):
        if not root:
            return 
        self.dfs(root.left)
        self.res.append(root.val)
        self.dfs(root.right)
    def inorderTraversal(self , root: TreeNode) -> List[int]:
        self.dfs(root)
        return self.res
发表于 2022-05-16 16:42:22 回复(0)
Python 3
牛客779086678号头像 牛客779086678号
Python递归过不了？
发表于 2022-05-05 12:02:21 回复(0)
Python 3
我是赵同学头像 我是赵同学
前中后序的排列只要改变加元素的位置即可 
import sys
sys.setrecursionlimit(10000)
class Solution:
    def __init__(self):
        self.l = []
    def inorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        if root == None:
            return
        self.inorderTraversal(root.left)
        self.l.append(root.val)
        self.inorderTraversal(root.right)
        
        return self.l


发表于 2022-04-06 17:47:39 回复(0)
Python 3
zero201801031535432头像 zero201801031535432 
class Solution:
    def inorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        if not root: return []
        stack = [root]
        ret = []
        while root.left:
            root = root.left
            stack.append(root)
        while stack:
            root = stack.pop()
            ret.append(root.val)
            if root.right:
                root = root.right
                stack.append(root)
                while root.left:
                    root = root.left
                    stack.append(root)
        return ret

发表于 2022-04-02 18:57:32 回复(0)
Python 3
TestNovice头像 TestNovice
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型一维数组
#
class Solution:
    def inorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        list_node =[]
        if root == None:
            return list_node
        else:
            list_node.append(root.val)
            return self.inorderTraversal(root.left) + list_node + self.inorderTraversal(root.right)

# 递归超过最大限度
发表于 2022-04-01 19:38:50 回复(0)
Python 3
Virtual~头像 Virtual~
class Solution:
    def inorderTraversal(self , root: TreeNode) -> List[int]:
        res = []
        stack = []
        if root:
            stack.append(root)
        
        while stack:
            node = stack.pop()
            if node != None:
                if node.right:
                    stack.append(node.right)
                stack.append(node)
                stack.append(None)
                if node.left:
                    stack.append(node.left)
            else:
                node = stack.pop()
                res.append(node.val)
        return res
发表于 2022-03-01 16:57:32 回复(0)
Python 3
秋招小拉吉头像 秋招小拉吉
你们都不会超时吗，为什么我python用中序遍历的递归模板第11个测试案例超时 
发表于 2022-03-01 14:13:06 回复(5)
Python 3
又要找工作了头像 又要找工作了 
class Solution:
    def inorderTraversal(self , root ):
        # write code here
        inorder = []
        if not root:
            return []
        def find(root):
            if not root:
                return None
            find(root.left)
            inorder.append(root.val)
            find(root.right)
        find(root)
        return inorder
为啥最后一个用例过不去呢？？求助各位朋友
发表于 2021-10-24 11:18:57 回复(1)
Python 3
我有班上啦头像 我有班上啦 
class Solution:
    def inorderTraversal(self , root, result = []):
        # write code here
        if root:
            if root.left:
                result = self.inorderTraversal(root.left)
            result.append(root.val)
            if root.right:
                result = self.inorderTraversal(root.right)
        return result

发表于 2021-09-05 15:41:42 回复(0)
提交观点

问题信息

树 dfs 递归 广度优先搜索(BFS)
难度：
19条回答 4805浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号